BCH (Bose-Chaudhuri-Hocquenghem) codes are a large class of multiple error-correcting codes. The binary BCH codes were discovered in 1959 by Hocquenghem and independently in 1960 by Bose and Ray-Chaudhuri. Later, Gorenstein and Zierler generalized them to all finite fields. At about the same time Reed and Solomon published their paper on the special case of BCH codes that now bear their names.
In practice, the binary BCH and Reed-Solomon codes are the most commonly used variants of BCH codes. They have applications in a variety of communication systems: space communication links, digital subscriber loops, wireless systems, networking communications, and magnetic and data storage systems. Continual demand for ever higher data rates and storage capacity provide an incentive to devise very high-speed and space-efficient VLSI implementations of BCH decoders. The first decoding algorithm for binary BCH codes was devised by Peterson in 1960. Since then, Peterson's algorithm has been refined by Gorenstein and Zierler, Berlekamp, Massey, Chien, Forney, and many others.
BCH codes are generally developed as follows. GF(q) is defined as a finite field of q elements, q=2s, called the base field, and α is defined as a primitive element of extension field GF(qm), where n|qm−1. The variable t is defined as an error detecting BCH code of length n over GF(q) as the set of all sequences (c0, c1, . . . , cn-1), ciεGF(q) such that polynomialc(x)=c0+c1x+ . . . +cn-1xn-1εGF(qm)[x]
has roots in points: α1, α2, . . . , α2t. The BCH code with m=1 is called the Reed Solomon code, and the BCH code with s=1 is called the binary BCH code.
Encoding of BCH Codes
First, we calculate the generator polynomial g(x)εGF(q):g(x)=(x−α)(x−α2) . . . (x−α2t)=LCM{M1(x), M2(x), . . . , M2t(x)},
where LCM is the least common multiplier and Mi(x) is the minimal polynomial for αi. Let (d0, d1, . . . , dk-1) denote k data symbols that are to be transmitted over a communication channel, and d(x)=d0+d1x+ . . . dk-1xk-1εGF(q)[x]. The systematic encoding of vector (d0, d1, . . . , dk-1) into a codeword (c0, c1, . . . , cn-1) is as follows:c(x)=xn-pd(x)+t(x),
where p=deg g(x) and t(x)=−xn-pd(x)mod g(x), c(x)=c0+c1x+ . . . +Cn-1xn-1.
Decoding of BCH Codes
There are many BCH decoder architectures. A typical BCH decoder works as follows. Let (c0, c1, . . . , Cn-1) be a transmitted codeword and (e0, e1, . . . , en-1) be an error vector in a communication channel, where in r (with r≦t) positions i1, i2, . . . , ir there are non-zero values Y1=ei1, . . . , Yr=eir. Let also X1=αi1, . . . , Xr=αi. Define e(x)=e0+e1x+ . . . +en-1xn-1 and t(x)=c(x)+e(x), t(x)=t0+t1x+ . . . +tn-1xn-1, where (t0, t1, . . . , tn-1) is a word is to be decoded. Then, the decoding algorithm consists of three main steps:
1. Syndrome Computation Block
The decoder begins by computing 2t syndrome valuesS0=c(α), S1=c(α2), . . . , S2t-1=c(α2t)2. Key Equation Solver Block
This block is perhaps the most intricate part of BCH decoder. Define the syndrome polynomial S(x), error locator polynomial Λ(x), and error evaluator polynomial Ω(x) as follows:
            S      ⁡              (        x        )              =                  S        0            +                        S          1                ⁢        x            +      …      +                        S                                    2              ⁢              t                        -            1                          ⁢                  x                                    2              ⁢              t                        -            1                                ,          ⁢            Λ      ⁡              (        x        )              =                            Λ          0                +                              Λ            1                    ⁢          x                +        …        +                              Λ            r                    ⁢                      x            r                              =                        ∑                      i            =            1                    r                ⁢                  (                      1            -                                          X                i                            ⁢              x                                )                      ,          ⁢            Ω      ⁡              (        x        )              =                            Ω          0                +                              Ω            1                    ⁢          x                +        …        +                              Ω                          r              -              1                                ⁢                      x                          r              -              1                                          =                        ∑                      i            =            1                    r                ⁢                              Y            i                    ⁢                      X            i                    ⁢                                    ∏                                                j                  =                  1                                ,                                  j                  ≠                  i                                            r                        ⁢                          (                              1                -                                                      X                    j                                    ⁢                  x                                            )                                          
It is well known that these three polynomials are related with the following key equation:Λ(x)S(x)=Ω(x)mod x2t 
There are two major methods for solving the key equation: first, the Berlekamp-Massey algorithm (BM), and second, the extended Euclidean algorithm (eE). Until recently the architectures based on the eE algorithm were more popular because of its simplicity and regularity. In addition, they had smaller critical path delays then architectures based on the BM algorithm. Lately, however, BM based architectures have gained in popularity, due to a number of modifications in the standard BM algorithm that have made them even faster and more space-efficient than the eE based architectures.
3. Chien/Forney Block
The last block finds the positions of the errors, and corrects the errors using the Forney formula:
            For      ⁢                          ⁢      all      ⁢                          ⁢      i        ∈                  {                  0          ,          1          ,          …          ⁢                                          ,                      n            -            1                          }            ⁢              :                        if      ⁢                          ⁢              Λ        ⁡                  (                      α                          -              i                                )                      =    0              then      ⁢                          ⁢              t        i              :=                  t        i            +                        Ω          ⁡                      (                          α                              -                i                                      )                                                Λ            ′                    ⁡                      (                          α                              -                i                                      )                                    else    ⁢                  ⁢    we    ⁢                  ⁢          don      '        ⁢    t    ⁢                  ⁢    change    ⁢                  ⁢                  t        i            .      
What is desired is a scalable architecture for the BM algorithm.